import java.util.*;
public class SAES {
	static int[][] w=new int[6][8];
	static int[] tempval=new int[8];
	static int[] subNib={9,4,10,11,13,1,8,5,6,2,0,3,12,14,15,7};
	static int[] xorval1={1,0,0,0,0,0,0,0};
	static int[] xorval2={0,0,1,1,0,0,0,0};
	static int[][][] SBOX_Encryption={
			{{1,0,0,1},{0,1,0,0},{1,0,1,0},{1,0,1,1},},
			{{1,1,0,1},{0,0,0,1},{1,0,0,0},{0,1,0,1},},
			{{0,1,1,0},{0,0,1,0},{0,0,0,0},{0,0,1,1},},
			{{1,1,0,0},{1,1,1,0},{1,1,1,1},{0,1,1,1},},
			};

	static int[][] subnib1={{1,0,0,1},
							{0,1,0,0},
							{1,0,1,0},
							{1,0,1,1},
							{1,1,0,1},
							{0,0,0,1},
							{1,0,0,0},
							{0,1,0,1},
							{0,1,1,0},
							{0,0,1,0},
							{0,0,0,0},
							{0,0,1,1},
							{1,1,0,0},
							{1,1,1,0},
							{1,1,1,0},
							{0,1,1,1},
		
	};
	static int[][] subnib2={{0,0,0,0},
		{0,0,0,0},
		{0,0,0,0},
		{1,0,1,1},
		{0,0,0,1},
		{0,0,0,0},
		{0,0,0,0},
		{0,0,0,0},
		{0,0,0,0},
		{0,0,0,0},
		{0,0,1,0},
		{0,0,0,0},
		{0,0,0,0},
		{0,0,0,0},
		{0,0,0,0},
		{0,0,0,0},

};
	static int[] K0=new int[16];
	static int[] K1=new int[16];
	static int[] K2=new int[16];
	static int[] ptext={1,1,0,1,0,1,1,1,0,0,1,0,1,0,0,0};//new int[16];
	static int[] ctext=new int[16];
	static int[] k={0,1,0,0,1,0,1,0,1,1,1,1,0,1,0,1};//new int[16];
	static int[] w0=new int[8];
	static int[] w1=new int[8];
	static int[] w2=new int[8];
	static int[] w3=new int[8];
	static int[] w4=new int[8];
	static int[] w5=new int[8];
	static int[] wp=new int[8];
public static void main(String args[])
{
	int i=0,N=0,x=0,y=0,z=0;;
	
	int[] xored;
	String[] ws = new String[10];
	
	Scanner sc=new Scanner(System.in);

	for(i=0;i<8;i++)
	{
		w0[i]=k[i];
		w1[i]=k[i+8];
	}
	
	for(i=0;i<8;i++)
	{
		w[0][i]=w0[i];
		w[1][i]=w1[i];
	}
	N=2;
	
	while(N<6)
	{
		if(N%2==0)
		{
			for(i=0;i<8;i++)
				wp[i]=w[N-1][i];
			
				tempval=subNib(rotNib(wp));
			if(N==2)
			{
				for(i=0;i<8;i++)
					w[N][i]=w[N-2][i]^xorval1[i]^tempval[i];
			}
			else if(N==4)
			{
				for(i=0;i<8;i++)
					w[N][i]=w[N-2][i]^xorval2[i]^tempval[i];
			}
		}
		else
		{
			for(i=0;i<8;i++)
			{
				w[N][i]=w[N-1][i]^w[N-2][i];
			}
		}
	
		N++;
	}
	for(i=0;i<16;i++)
	{
		if(i<8)
		{
			K0[i]=w[0][i];
			K1[i]=w[2][i];
			K2[i]=w[4][i];
		}
		else 
		{
			K0[i]=w[1][x];
			K1[i]=w[3][x];
			K2[i]=w[5][x];
			x++;
		}
	}
	System.out.println("K0 is: ");
	for(i=0;i<16;i++)
	{
		System.out.print(K0[i]+",");
	}
	System.out.println("\nK1 is: ");
	for(i=0;i<16;i++)
	{
		System.out.print(K1[i]+",");
	}
	System.out.println("\nK2 is: ");
	for(i=0;i<16;i++)
	{
		System.out.print(K2[i]+",");
	}
	ctext=encrypt();
	System.out.println("\n\nThe Cipher Text is: ");
	for(int f = 0;f<16;f++)
	{
		System.out.print(ctext[f]+",");
	}
	
	ptext=decrypt();
	
}
static int[] encrypt()
{
	int [][][] Me={{{0,0,0,1},{0,1,0,0}},{{0,1,0,0},{0,0,0,1}}};
	int[] xored = new int[ptext.length];
	int[] Result=new int[16];
	xored=XOR(ptext,K0);
	
	Result=round(ptext,xored);
	Result=Final_Round(Result);
	return Result;
	
}
static int[] decrypt()
{
	int [][] IMe={{2,9},{9,2}};
	int[] Result=new int[16];
	Result=ctext;
	Result=ARK2(Result);
	Result=swapNib(Result, 2, 4);
	Result=subNib_for_decryption(Result);
	
	
	Result=ARK1(Result);
	Result=MixColumn(Result,IMe);
	System.out.println("Result Array after Inverse Mix Column is: ");
	for(int i=0;i<16;i++)
	{
		System.out.print(Result[i]+",");
	}
	return Result;
}
static int[] Final_Round(int[] Output)
{
	Output=subNib(Output);
	swapNib(Output, 2, 4);
	Output=ARK2(Output);
	return Output;
}
static int[] ARK2(int[] temp)
{
	int[] XOR_With={1,0,0,0,0,1,1,1,1,0,1,0,1,1,1,1};
	temp=XOR(temp,XOR_With);
	return temp;
}
static int[] round(int[] ptext,int[] xored)
{
	int [][] Me={{1,4},{4,1}};
	int[] output=new int[16];
	int[] temp1=new int[8];
	int[] temp2=new int[8];
	int[][][] S=new int[2][2][4];
	int[] Result=new int[16];
	int i=0;
	for(i=0;i<8;i++)
	{
		temp1[i]=xored[i];
		temp2[i]=xored[i+8];
	}
	temp1=subNib(temp1);
	temp2=subNib(temp2);
	for(i=0;i<8;i++)
	{
		output[i]=temp1[i];
		output[i+8]=temp2[i];
	}
	/*System.out.println("\nOutput is: ");
	for(i=0;i<16;i++)
	{
		System.out.print(output[i]+",");
	}*/
	output=swapNib(output,2,4);
	/*System.out.println("\nOutput after swapping 2nd and 4th nibbles is: ");
	for(i=0;i<16;i++)
	{
		System.out.print(output[i]+",");
	}*/
	int f=0;
	/*for(i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			for(int k=0;k<4;k++)
			{
				S[i][j][k]=output[f];
				f++;
			}
		}
	}
	mulmat(S,Me);*/
	Result=MixColumn(output,Me);
	Result=ARK1(Result);
	/*System.out.println("Result After ARK1 is : ");
	for(int j=0;j<16;j++)
	{
		System.out.print(Result[j]+",");
	}*/
	return Result;
	/*System.out.println("\nThe S array is: ");
	for(i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			for(int k=0;k<4;k++)
			{
				System.out.print("S["+i+"]"+"["+j+"]"+"["+k+"]"+S[i][j][k]+"  ");
			}
			System.out.println("");
		}
	}*/
	
}
static int[] ARK1(int[] temp)
{
	int[] XOR_With={1,1,0,1,1,1,0,1,0,0,1,0,1,0,0,0};//{1},{1},{0},{1},{1},{1},{0},{1},{0},{0},{1},{0},{1},{0},{0},{0}};
	temp=XOR(temp,XOR_With);
	return temp;
}
static int[] MixColumn(int[] output,int[][] Me)
{
	int[] S_val=new int[4];
	int[] divident=new int[8]; 
	int[] A=new int[8],B=new int[8];
	int[] S_New=new int[8];
	int[] Result=new int[16];
	String temp;
	for (int k= 0; k < output.length; k += 4) {
		S_val[k / 4] = output[k] * 1000 + output[k + 1] * 100 + output[k + 2] * 10 + output[k + 3];
	}
	
	int s1=BToD(S_val[0]);
	int s2=BToD(S_val[1]);
	int s3=BToD(S_val[2]);
	int s4=BToD(S_val[3]);
	int k1=3,h=0;
	// to multiply with M matrix
	int[][] S = { { s1, s3 }, { s2, s4 } };
	int[][] multiply = new int[2][2];
	int sum = 0,count=0;
	for (int c = 0; c < 2; c++) {
		for (int d = 0; d < 2; d++) {
			for (int k = 0; k < 2; k++) {
				count++;
				//System.out.println("Count= "+count);
				if(k==0)
				{
					k1=3;
					temp=String.format("%4s",Integer.toBinaryString(Me[c][k] * S[k][d])).replace(' ', '0');
					if((Me[c][k] * S[k][d])<=15)
					{
						for(int i=7;i>=4;i--)
						{
							if(k1>=0)
							{
								A[i]=Integer.parseInt(String.valueOf((temp.charAt(k1))));
								k1--;
							}
						}
					}
					else if(Me[c][k]>1 && (Me[c][k] * S[k][d])>15){
						//String a=Integer.toBinaryString(Me[c][k] * S[k][d]);
						//System.out.println("\ntemp="+temp);
						A=polydiv(temp,"10011");
					}
				}
				else if(k==1)
				{
					//B=Me[c][k] * S[k][d];
					temp=String.format("%4s",Integer.toBinaryString(Me[c][k] * S[k][d])).replace(' ', '0');
					k1=3;
					if((Me[c][k] * S[k][d])<=15)
					{
						for(int i=7;i>=4;i--)
						{
							if(k1>=0)
							{
								B[i]=Integer.parseInt(String.valueOf(temp.charAt(k1)));
								k1--;
							}
						}
					}
					else if(Me[c][k]>1 &&  (Me[c][k] * S[k][d])>15){
						String a=Integer.toBinaryString( (Me[c][k] * S[k][d]));
						//System.out.println("\na="+a);
						B=polydiv(temp,"10011");
				}
				//sum = sum + Me[c][k] * S[k][d];
			}
				

			/*multiply[c][d] = sum;
			System.out.println("\nmultiply[" + c + "][" + d + "]= " + sum);
			sum = 0;*/
		}
			S_New=XOR(A,B);
			System.out.println("S_New is : ");
			for(int i=0;i<8;i++)
			{
				System.out.print(S_New[i]+",");
			}
			/*for(int y=0,g=7;y<8;y++,g--)
			{
				Result[h]=(int) (sum+S_New[y]*Math.pow(2,g));
				h++;
			}*/
			for(int y=4;y<=7;y++)
			{
				Result[h]=S_New[y];
				h++;
			}
		}
		
		
	}
	Result=swapNib(Result, 2, 3);
	System.out.println("Result is: ");
	for(int y=0;y<16;y++)
	{
		System.out.print(Result[y]+",");
	}
	
	return Result;
}
static int[] polydiv(String divid,String divis)
{
			int[] dividend=new int[8];
			int[] divisor=new int[8];
			int degDivisor=0,degDividend=0;
			int i=0,k=divid.length()-1,l=divis.length()-1;
			//System.out.println("\nDividend"+divid);
			//System.out.println("divisor"+divis);
			int diff=0;
			int temp=0;
			int[] multiplied=new int[8];
			for(i=7;i>=0;i--)
			{
				if(k>=0)
				{
					dividend[i]=Integer.parseInt(String.valueOf(divid.charAt(k)));
					k--;
				}
			}
			for(i=0;i<8;i++)
			{
				//System.out.println("dividend["+i+"]"+dividend[i]);
			}
			for(i=7;i>=0;i--)
			{
				if(l>=0)
				{
					divisor[i]=Integer.parseInt(String.valueOf(divis.charAt(l)));
					l--;
				}
			}
			for(i=0;i<8;i++)
			{
				//System.out.println("divisor["+i+"]"+divisor[i]);
			}
		
		while(true)
		{
			for(i=0;i<8;i++)
			{
				if(dividend[i]==1)
				{
					degDividend=7-i;
					break;
				}
			}
			for(i=0;i<8;i++)
			{
				if(divisor[i]==1)
				{
					degDivisor=7-i;
					break;
				}
			}
			if(degDivisor>degDividend)
				break;
			System.out.println("degree of dividend is= "+degDividend);
			System.out.println("degree of divisor is= "+degDivisor);
			diff=degDividend-degDivisor;
			if(diff<0)
				diff=-diff;
			for(i=0;i<8;i++)
			{
				multiplied[i]=divisor[i];
			}
			for(i=0;i<diff;i++)
			{
				if(diff!=0)
				multiplied=leftShift(multiplied);
			}
			System.out.println("Array after left shift");
			for(i=0;i<8;i++)
			{
				System.out.print(multiplied[i]+" ");
			}
			dividend=XOR(multiplied,dividend);
			System.out.println("\nArray after XOR");
			for(i=0;i<8;i++)
			{
				System.out.print(dividend[i]+" ");
			}
		}
	return dividend;
}
public static int[] leftShift(int[] var) {
	int temp=0;
	//temp=var[0];
	for(int i=0;i<var.length;i++)
	{
		if(i!=var.length-1)
		{
			var[i]=var[i+1];
		}
		else if(i==var.length-1)
		{
			var[i]=0;
		}
		
}
	return var;
}
public static int BToD(int bNum) {

	int dec=0;
	int f=0;
	while (true) {
		if (bNum == 0) {
			break;
		} else {
			int temp = bNum % 10;
			dec += temp * Math.pow(2, f);
			bNum = bNum / 10;
			f++;
		}
	}
	return dec;
}
static int[] swapNib(int[] input,int i,int j)
{
	int temp=0;
	for(int h=0;h<4;h++)
	{
		temp=input[(i-1)*4 + h];
		input[(i-1)*4 + h]=input[(j-1)*4 + h];
		input[(j-1)*4 + h]=temp;
	}
	return input;
	
}
static int[] XOR(int[] ptext,int[] k0)
{
	int[] kxp=new int[ptext.length];
	int i=0;
	for(i=0;i<ptext.length;i++)
		kxp[i]=ptext[i]^k0[i];
	return kxp;
}
static int[] rotNib(int [] c)
{
	int temp=0;
	for(int i=0;i<4;i++)
	{
		temp=c[i];
		c[i]=c[i+4];
		c[i+4]=temp;
	}
	
	return c;
}
/*static int[] subNib(int[] val)
{
	int i=val.length-1,temp=0,j=0,k=val.length-1,index1=0;
	int[] result=new int[val.length];
	while(i>=0)
	{
		if((i+1)%4!=0 || temp==0)
		{
			temp=temp+val[i]*(int)Math.pow(2,index1);
			index1++;
		}
		else if((i+1)%4==0 && temp!=0)
		{
			k=i;
			for(j=0;j<4;j++,k++)
				result[k]=subnib1[temp][j];
			index1=0;
			temp=0;
			i++;
		}
		i--;
	}
	for(i=0;i<val.length;i++)
	{
		System.out.print(result[i]+",");
	}
	System.out.println("");
	return result;
}*/
static int[] subNib_for_decryption(int[] val)
{
	int temp1=0,temp2=0,index1=0,index2=0,i=0,j=0,j1=0,temp3=0,temp4=0,index3=0,index4=0,j3=0,j2=0;
	if(val.length==8)
	{
		for(i=7;i>=0;i--)
		{
			if(i<4)
			{
				temp1=temp1+val[i]*(int)Math.pow(2,index1);
				index1++;
			}
			else{
				
				temp2=temp2+val[i]*(int)Math.pow(2,index2);
				index2++;
			}
		}
		//System.out.println("temp1== "+temp1+" & "+"temp2=="+temp2);
		for(i=0;i<8;i++)
		{
			if(i<4)
			{
				val[i]=subnib2[temp1][j];
				j++;
			}
			else{
				
				val[i]=subnib2[temp2][j1];
				j1++;
			}
		}
		/*for(i=0;i<8;i++)
		{
			System.out.print(val[i]+",");
		}
		System.out.println("");*/
	}
	else if(val.length==16)
	{
		for(i=15;i>=0;i--)
		{
			if(i<4)
			{
				temp1=temp1+val[i]*(int)Math.pow(2,index1);
				index1++;
			}
			else if(i>=4 && i<8){
				
				temp2=temp2+val[i]*(int)Math.pow(2,index2);
				index2++;
			}
			else if(i>=8 && i<12)
			{
				temp3=temp3+val[i]*(int)Math.pow(2,index3);
				index3++;
			}
			else if(i>=12 && i<16)
			{
				temp4=temp4+val[i]*(int)Math.pow(2,index4);
				index4++;
			}
		}
		//System.out.println("temp1== "+temp1+" & "+"temp2=="+temp2+" & "+"temp3=="+temp3+" & "+"temp4=="+temp4);
		for(i=0;i<16;i++)
		{
			if(i<4)
			{
				val[i]=subnib2[temp1][j];
				j++;
			}
			else if(i>=4 && i<8){
				
				val[i]=subnib2[temp2][j1];
				j1++;
			}
			else if(i>=8 && i<12)
			{
				val[i]=subnib2[temp3][j2];
				j2++;
			}
			else if(i>=12 && i<16)
			{
				val[i]=subnib2[temp4][j3];
				j3++;
			}
		}
		/*for(i=0;i<val.length;i++)
		{
			System.out.print(val[i]+",");
		}
		System.out.println("");*/
	}
	return val;
	/*
		System.out.println("temp1== "+temp1+" & "+"temp2=="+temp2);
		for(i=0;i<15;i++)
		{
			if(temp1==subNib[i])
			{
				index1=subNib[i];
			}
			if(temp2==subNib[i])
			{
				index2=subNib[i];
			}
		}
		for(i=0;i<8;i++)
		{
			if(i<4)
			{
				while(index1 > 0){
		            val[i++] = index1%2;
		            index1 = index1/2;
		        }
			}
			else
			{
				while(index2 > 0){
		            val[i++] = index2%2;
		            index2 = index2/2;
		        }
			}
		}
		System.out.println("Val array is: ");
		for(i=0;i<8;i++)
		{
			System.out.print(val[i]+",");
		}
		System.out.println("");
	
	return val;
*/	
	
}
static int[] subNib(int[] val)
{
	int temp1=0,temp2=0,index1=0,index2=0,i=0,j=0,j1=0,temp3=0,temp4=0,index3=0,index4=0,j3=0,j2=0;
	if(val.length==8)
	{
		for(i=7;i>=0;i--)
		{
			if(i<4)
			{
				temp1=temp1+val[i]*(int)Math.pow(2,index1);
				index1++;
			}
			else{
				
				temp2=temp2+val[i]*(int)Math.pow(2,index2);
				index2++;
			}
		}
		//System.out.println("temp1== "+temp1+" & "+"temp2=="+temp2);
		for(i=0;i<8;i++)
		{
			if(i<4)
			{
				val[i]=subnib1[temp1][j];
				j++;
			}
			else{
				
				val[i]=subnib1[temp2][j1];
				j1++;
			}
		}
		/*for(i=0;i<8;i++)
		{
			System.out.print(val[i]+",");
		}
		System.out.println("");*/
	}
	else if(val.length==16)
	{
		for(i=15;i>=0;i--)
		{
			if(i<4)
			{
				temp1=temp1+val[i]*(int)Math.pow(2,index1);
				index1++;
			}
			else if(i>=4 && i<8){
				
				temp2=temp2+val[i]*(int)Math.pow(2,index2);
				index2++;
			}
			else if(i>=8 && i<12)
			{
				temp3=temp3+val[i]*(int)Math.pow(2,index3);
				index3++;
			}
			else if(i>=12 && i<16)
			{
				temp4=temp4+val[i]*(int)Math.pow(2,index4);
				index4++;
			}
		}
		//System.out.println("temp1== "+temp1+" & "+"temp2=="+temp2+" & "+"temp3=="+temp3+" & "+"temp4=="+temp4);
		for(i=0;i<16;i++)
		{
			if(i<4)
			{
				val[i]=subnib1[temp1][j];
				j++;
			}
			else if(i>=4 && i<8){
				
				val[i]=subnib1[temp2][j1];
				j1++;
			}
			else if(i>=8 && i<12)
			{
				val[i]=subnib1[temp3][j2];
				j2++;
			}
			else if(i>=12 && i<16)
			{
				val[i]=subnib1[temp4][j3];
				j3++;
			}
		}
		/*for(i=0;i<val.length;i++)
		{
			System.out.print(val[i]+",");
		}
		System.out.println("");*/
	}
	return val;
	/*
		System.out.println("temp1== "+temp1+" & "+"temp2=="+temp2);
		for(i=0;i<15;i++)
		{
			if(temp1==subNib[i])
			{
				index1=subNib[i];
			}
			if(temp2==subNib[i])
			{
				index2=subNib[i];
			}
		}
		for(i=0;i<8;i++)
		{
			if(i<4)
			{
				while(index1 > 0){
		            val[i++] = index1%2;
		            index1 = index1/2;
		        }
			}
			else
			{
				while(index2 > 0){
		            val[i++] = index2%2;
		            index2 = index2/2;
		        }
			}
		}
		System.out.println("Val array is: ");
		for(i=0;i<8;i++)
		{
			System.out.print(val[i]+",");
		}
		System.out.println("");
	
	return val;
*/	
	
}
}
/*
Enter the plaintext
1 1 0 1 0 1 1 1 0 0 1 0 1 0 0 0
Enter the Key
0 1 0 0 1 0 1 0 1 1 1 1 0 1 0 1
W0 is :0 1 0 0 1 0 1 0 
W1 is :1 1 1 1 0 1 0 1 temp1== 5 & temp2==15
0,0,0,1,0,1,1,1,
w[2]is: 
1,1,0,1,1,1,0,1,w[3]is: 
0,0,1,0,1,0,0,0,temp1== 8 & temp2==2
0,1,1,0,1,0,1,0,
w[4]is: 
1,0,0,0,0,1,1,1,w[5]is: 
1,0,1,0,1,1,1,1,K0 is: 
0,1,0,0,1,0,1,0,1,1,1,1,0,1,0,1,
K1 is: 
1,1,0,1,1,1,0,1,0,0,1,0,1,0,0,0,
K2 is: 
1,0,0,0,0,1,1,1,1,0,1,0,1,1,1,1,/nAdd Round 0 key
1,0,0,1,1,1,0,1,1,1,0,1,1,1,0,1,temp1== 9 & temp2==13
0,0,1,0,1,1,1,0,
temp1== 13 & temp2==13
1,1,1,0,1,1,1,0,

Output is: 
0,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,
Output after swapping 2nd and 4th nibbles is: 
0,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,
 */